package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * 1092. 最短公共超序列
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/17 16:16
 */
public class ShortestCommonSupersequence {


    public static void main(String[] args) {
        ShortestCommonSupersequence test = new ShortestCommonSupersequence();

        // cabac
        String str1 = "abac";
        String str2 = "cab";

        String s = test.shortestCommonSupersequence(str1, str2);
        System.out.println(s);

    }

    public String shortestCommonSupersequence(String str1, String str2) {
        char[] as = str1.toCharArray();
        char[] bs = str2.toCharArray();
        int a = as.length;
        int b = bs.length;
        int[][] dp = new int[a + 1][b + 1];
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                if (as[i] == bs[j]) {
                    int c = dp[i][j] & 0X3FF;
                    dp[i + 1][j + 1] = (i << 20) + (j << 10) + c + 1;
                } else {
                    int v1 = dp[i + 1][j] & 0X3FF;
                    int v2 = dp[i][j + 1] & 0X3FF;
                    if (v1 >= v2) {
                        dp[i + 1][j + 1] = ((i + 1) << 20) + (j << 10) + v1;
                    } else {
                        dp[i + 1][j + 1] = (i << 20) + ((j + 1) << 10) + v2;
                    }
                }
            }
        }
        int v = dp[a][b];
        int l = v & 0X3FF;
        if (l == 0) {
            return str1 + str2;
        }
        int[] arr1 = new int[l];
        int[] arr2 = new int[l];
        while (v != 0) {
            int x = v >> 20;
            int y = (v >> 10) & 0X3FF;
            int c = v & 0X3FF;
            if (c == 0) {
                break;
            }
            arr1[c - 1] = x;
            arr2[c - 1] = y;
            v = dp[x][y];
        }
        StringBuilder sb = new StringBuilder(a + b - l);
        int at = 0;
        int bt = 0;
        for (int i = 0; i < l; i++) {
            sb.append(str1, at, arr1[i]);
            sb.append(str2, bt, arr2[i]);
            sb.append(as[arr1[i]]);
            at = arr1[i] + 1;
            bt = arr2[i] + 1;
        }
        sb.append(str1.substring(at));
        sb.append(str2.substring(bt));
        return sb.toString();
    }

}
